1. Field of the Invention
The invention relates to an ACS (Add-Compare-Select) circuit, and in particular to an ACS circuit, in which an adder and a comparator are processing in parallel to increase the processing speed thereof, thereby increasing the processing speed of a Viterbi decoder with the ACS circuit.
2. Description of the Related Art
A PRML (Partial Response Maximum Likelihood) system is used to retrieve EFM (Eight-to-Fourteen Modulation) signals from CD (Compact Disc)/DVD (Digital Versatile Disk). In the PRML system, a Viterbi decoder is usually used to realize the maximum likelihood detection.
FIG. 1(A) is a block diagram showing a conventional Viterbi decoder. Referring to this drawing, a Viterbi decoder typically includes a branch metric generator 11, an ACS (Add-Compare-Select) unit 12, and a survivor path memory and decoding unit 13. The branch metric generator 11 calculates the metrics corresponding to each branch according to the received data, and outputs them to the ACS unit 12. The branch metric generator 11 calculates the distance, such as mean-square-distance, between the received data and the estimated data of the branch. For each state, the ACS unit 12 adds the branch metrics of input branches with the related state metric to generate the candidate state metrics, compares and selects the minimum of the candidate state metrics as the new state metric. The decision bit of the ACS unit 12, indicating the decision of the state-metric selection, is sent to the survivor path memory and decoding unit 13. According to the decision bit, the survivor paths of the survivor path memory and decoding unit 13 are updating to keep consistent with the selected result of related state metric. The survivor memory and decoding unit 13 restores the decoded results corresponding to each state, and a decoding unit executes the majority vote for the ending bits of all survivor paths to decide the output decoded result.
FIG. 1(B) is an architecture diagram showing an ACS processor in the ACS unit of FIG. 1(A), wherein SMi(n−1) and SMj(n−1) are state metrics of state Si and state Sj at time n−1, respectively, and BMi,k(n−1) and BMj,k(n−1) are branch metrics from state Si to state Sk at time n−1 and from state Sj to state Sk at time n−1, respectively. The SMk(n) is a state metric at time n and the BMk,m(n) is the branch metric from state Sk to state Sm at time n. In this drawing, it illustrates that the ACS processor is used to select the survivor state metric from either state Si or state Sj. As shown in the drawing, an ACS processor 14 in an ACS unit 12 includes two adders 15, 15′, a comparator 16, and a selector 17. The ACS processor 14 employs the adder 15 to add SMi(n−1) to BMi,k(n−1) to generate a first candidate state metric, and the adder 15′ to add SMj(n−1) to BMj,k(n−1) to generate a second candidate state metric. Then, the ACS processor 14 employs the comparator 16 and selector 17 to compare the first candidate state metric with the second candidate state metric, and select the minimum to be outputted to a state register 18 as the SMk(n). The comparison result, serving as a decision bit, is outputted to the survivor memory and decoding unit 13. The adder 19 belongs to another ACS processor 14′.
FIG. 2(A) shows a 4-state trellis diagram, and FIG. 2(B) is a block diagram showing the ACS unit 12 in the Viterbi decoder corresponding to the trellis diagram of FIG. 2(A). Since FIG. 2(A) is a 4-state trellis diagram, the ACS unit 12 includes four ACS processors 121 to 124 and four state registers 125 to 128 for storing the state metrics S0 to S3, as shown in FIG. 2(B). In addition to transferring the generated metrics back to the state registers 125 to 128, the ACS processors 121 to 124 of the ACS unit 12 further output decision bits to the survivor memory and decoding unit 13. The ACS processor 121 receives the state metrics from the state registers 125 and 127, adds together the state metrics and the related branch metrics, selects a smaller addition result as a survivor metric, stores back to the state register 125, and outputs the comparison value (logic 1 or logic 0) serving as a decision bit simultaneously. The ACS processor 122 receives the state metrics from the state register 125 and 127, adds together the state metrics and the related branch metrics, selects a smaller addition result as a survivor metric, stores back to the state register 126, and outputs a comparison value (logic 1 or logic 0) serving as a decision bit simultaneously. The processing methods for the ACS processors 123 and 124 are also the same.
FIG. 3 shows a circuit of the ACS processor as shown in FIG. 2(B). Referring to FIG. 3, the ACS processor 121 includes two adders 1211, 1211′, a comparator 1212 and a multiplexer 1213. The adders 1211, 1211′ are used to add together the branch metric and the state metric, and the comparator 1212 is used to compare two output values from the adders 1211, 1211′. The multiplexer 1213 selects a value from the output values of the two adders 1211, 1211′ as a new state metric according to the comparison result of the comparator 1212. Meanwhile, the comparison result of the comparator 1212 also serves as a decision bit for output. From FIG. 1(B) and FIG. 3, it is shown that the execution order of the ACS processor is Add→Compare→Select. Because the execution of comparison needs to wait the result of addition, the addition and comparison cannot be executed in parallel, which is a timing bottleneck of a conventional ACS unit.
In the application of decoding an EFM signal, the EFM signal has the property of run length limited (RLL) that the minimum run length of an EFM signal is 3 T, where T is a recording unit length. When decoding with respect to the EFM signal, a simplified trellis diagram can be obtained according to the RLL of the EFM signal, as shown in FIG. 4(A). That is, the trellis diagram has six states including state S0(000), state S1(001), state S2(011), state S3(100), state S4(110), and state S5(111), in which the states of (010) and (101) are invalid and not listed due to the minimum run length of 3 T. In addition, state S1(001), state S2(011), state S3(100) and state S4(110) only have a branch. FIG. 4(B) is a schematic illustration showing the branch values corresponding to the trellis diagram of FIG. 4(A). The Viterbi decoder generates all possible input sequences from the trellis diagram, and selects the most possible result as the decoded result. According to the trellis diagram of FIG. 4(A), only state S0 and state S5 receive two input values, so the state S0 and state S5 have to judge and select one of the input sequences.
FIG. 5 is an architecture diagram showing a Viterbi decoder applied to the trellis diagram of FIG. 4(A). Referring to the drawing, the Viterbi decoder includes an ACS unit 52 and a survivor memory and decoding unit 13. Because the trellis diagram has already been simplified due to the property of RLL, the ACS unit 52 only includes two ACS processors 521 and 522, two adders 523 and 524, and six registers 525 to 530. The ACS processor 521 receives the state metrics of state S0 and state S3, adds together the state metrics and the related branch metrics, selects a smaller result through the compare-select circuit 5211, and stores the selected result back to the register 525 at state S0. Next, the ACS processor 521 outputs the comparison value, serving as a decision bit, from the compare-select circuit 5211 to the multiplexers in the path 0 of the survivor memory and decoding unit 13. The ACS processor 522 receives the state metrics of state S2 and state S5, adds together the state metrics and the branch metrics, selects a smaller result through the compare-select circuit 5221, and stores the selected result back to the register 530 at state S5. Next, the ACS processor 522 outputs the comparison value, serving as a decision bit, from the compare-select circuit 5221 to the multiplexers in the path 5 of the survivor memory and decoding unit 13. Since the trellis diagram has been simplified, the multiplexers are only arranged in path 0 and path 5 of the survivor memory and decoding unit 13. Other paths 1 to 4 are only used to transfer data directly to another path memory. The survivor memory and decoding unit 13 employs a decision circuit 131, which may be a majority vote circuit, to vote the majority of bit value of the ending bits of six survivor paths as decoded data for output.
U.S. Pat. No. 6,148,431 titled “Add compare select circuit and method implementing a Viterbi algorithm” disclosed an ACS circuit with parallel process in the adder and comparator. In this architecture, the trellis diagram must satisfy the condition that the branch metrics for the ACS unit have to be equal. That is, the ACS unit in the U.S. Pat. No. 6,148,431 is not an ACS unit for general purpose.
In general, the conventional ACS unit is the bottleneck of processing speed of the Viterbi decoder, and the ACS processor of the ACS unit cannot increase the processing speed by way of direct pipelining or parallel processing.